// https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
// 236. Lowest Common Ancestor of a Binary Tree
// Given a binary tree, find the lowest common ancestor (LCA) of two given nodes
// in the tree.
import { TreeNode } from '../utils/index.ts';
function lowestCommonAncestor(
    root: TreeNode | null,
    p: TreeNode | null,
    q: TreeNode | null
): TreeNode | null {
    if (root === null) return null;

    const parent: Map<number, TreeNode> = new Map();
    const set: Set<number> = new Set();

    function dfs(root: TreeNode): void {
        if (root.left) {
            parent.set(root.left.val, root);
            dfs(root.left);
        }

        if (root.right) {
            parent.set(root.right.val, root);
            dfs(root.right);
        }
    }
    dfs(root);

    while (p) {
        set.add(p.val);
        p = parent.get(p.val) || null;
    }

    while (q) {
        if (set.has(q.val)) {
            return q;
        }
        q = parent.get(q.val) || null;
    }

    return null;
}
